package com.yq.leetcodeOld.tree;

import java.util.*;

/**
 * @ClassName Solution103
 * @Description TODO
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[20,9],[15,7]]
 * @Author yaoqiang
 * @Date 2022/2/21 10:22
 * @Version 1.0
 */
public class Solution103 {
    public static void main(String[] args) {

    }
    public List< List<Integer>> zigzagLevelOrder(TreeNode root){
        List<List<Integer>> ans= new LinkedList<>();//声明双向列表，包含前一个节点和后一个节点的引用
        if(root==null){return  ans;}
        Queue<TreeNode> nodeQueue=new LinkedList<>();
        nodeQueue.offer(root);
        boolean isOrderLeft=true;
        while (!nodeQueue.isEmpty()){
            Deque<Integer> levelList=new LinkedList<>();
            int size=nodeQueue.size();
            for (int i=0;i<size;i++){
                TreeNode curNode=nodeQueue.poll();
                if (isOrderLeft){levelList.offerLast(curNode.val);}else {levelList.offerFirst(curNode.val);}
                if (curNode.left!=null){nodeQueue.offer(curNode.left);}
                if (curNode.right!=null){nodeQueue.offer(curNode.right);}
            }
            ans.add(new LinkedList<>(levelList));
            isOrderLeft=!isOrderLeft;//取反赋值
        }
        return ans;
    }
//
//                if (curNode.left != null) {
//                    nodeQueue.offer(curNode.left);
//                }
//                if (curNode.right != null) {
//                    nodeQueue.offer(curNode.right);
//                }
//            }
//            ans.add(new LinkedList<Integer>(levelList));
//            isOrderLeft = !isOrderLeft;
//        }
//
//        return ans;
//    }


}


   /* public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        vector<vector<int>> ans;
        if(!root) return ans;
        bool left_flag = true;//是否从左至右标志位
        queue<TreeNode> que;//队列实现BFS按层遍历
        que.push(root);
        while(!que.empty()){
            //定义一个双端队列存储当前层的值，用双端队列是方便按层存值调换方向
            deque<int> dlist;
            //获取当前层值的个数，用来一次遍历完该层
            int n = que.size();
            //遍历队列中该层的值并出队，按标志位存入双端队列，再按固定顺序读取下一层节点值进队列
            for(int i = 0; i < n; i++){
                auto node = que.front();//取节点
                que.pop();//出队
                //按要求存
                if(left_flag){
                    dlist.push_back(node.val);//存入顺序和读取下一层顺序一致
                }else{
                    dlist.push_front(node.val);//反向存入双端队列
                }
                //读取下一层节点值进入队列(左至右)
                if(node.left) que.push(*node.left);
                if(node.right) que.push(*node.right);
            }
            ans.push_back(vector<int>{dlist.begin(), dlist.end()});//存入ans中，勿忘格式转换
            left_flag = !left_flag;//标志位转换
        }
        return ans;
    }*/